package 面试相关;

import java.util.Comparator;
import java.util.PriorityQueue;

public class 最小k个数 {
    public static void main(String[] args) {
        int[] nums = new int[]{3,6,5,4,1,2,9,7,8,0};
        quickSort(nums,0,nums.length - 1);
        for(int i : nums){
            System.out.print(i);
        }
    }
    public static void quickSort(int[] nums, int i, int j){
        if(i > j){
            return ;
        }
        int temp = nums[i];
        int start = i,end = j;
        while (start < end){
            while (nums[end] >= temp && start < end){
                end--;
            }
            while (nums[start] <= temp && start < end){
                start++;
            }
            if(start < end){
                int t = nums[start];
                nums[start] = nums[end];
                nums[end] = t;
            }
        }
        nums[i] = nums[start];
        nums[start] = temp;
        quickSort(nums,i,start - 1);
        quickSort(nums,start + 1,end);
    }
    public int[] smallestK(int[] arr, int k) {
        int[] res = new int[k];
        if(k == 0){
            return res;
        }
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2){
                return o2 - o1;
            }
        });
        for(int i = 0; i < k; i++){
            queue.offer(arr[i]);
        }
        for(int i = k; i < arr.length; i++){
            int num = queue.peek();
            if(num > arr[i]){
                queue.poll();
                queue.offer(arr[i]);
            }
        }
        for(int i = 0; i < k; i++){
            res[i] = queue.poll();
        }
        return res;
    }

}
